package com.hyper_yang.algorithmRecord.backTrack;

import java.util.*;

// leetcode 207 课程表 【拓扑排序】 【广度优先搜索】
public class CourseSchedule {
    /*
    你这个学期必须选修 numCourses门课程，记为 0到 numCourses - 1。
    在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，
    其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
    例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
    请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。
     */
    // 方法一: BFS
    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        // 定义数组保存所有节点 入度
        int[] inDegrees = new int[numCourses];
        // 定义一个 HashMap存储邻接矩阵
        HashMap<Integer, ArrayList<Integer>> followUpCourses = new HashMap<>();
        // 1、遍历先决条件，计算入读和后续节点
        for (int[] prerequisite : prerequisites) {
            inDegrees[prerequisite[0]]++;  // 后修课程入度 +1
            // 获取先修课程的后续节点列表
            ArrayList<Integer> followUpCourseList = followUpCourses.getOrDefault(prerequisite[1], new ArrayList<>());
            followUpCourseList.add(prerequisite[0]);  // 后修课程加入列表
            followUpCourses.put(prerequisite[1], followUpCourseList);
        }
        // 定义队列保存当前可以学习的课程，入读为 0的课程
        LinkedList<Integer> selectableCourses = new LinkedList<>();
        // 2、启动 BFS，将入度为 0的所有课程入队
        for (int i = 0; i < numCourses; i++) {
            if (inDegrees[i] == 0)
                selectableCourses.offer(i);
        }
        // 记录以学习的课程数量
        int finishedCourseNum = 0;
        // 3、不停的出队（学习课程），将后续课程入度 -1，并将新的入度为 0的课程入队
        while (!selectableCourses.isEmpty()) {
            int course = selectableCourses.poll();
            finishedCourseNum++;
            // 遍历当前课程的后续课程，入度 -1
            for (Integer followUpCourse : followUpCourses.getOrDefault(course, new ArrayList<>())) {
                inDegrees[followUpCourse]--;
                // 如果当前后续课程入读减为 1，入队
                if (inDegrees[followUpCourse] == 0)
                    selectableCourses.offer(followUpCourse);
            }
        }
        return finishedCourseNum == numCourses;
    }

    // 方法二: DFS
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, ArrayList<Integer>> followUpCourses = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            // 获取后续节点列表
            ArrayList<Integer> followUpCourseList = followUpCourses.getOrDefault(prerequisite[1], new ArrayList<>());
            followUpCourseList.add(prerequisite[0]);
            followUpCourses.put(prerequisite[1], followUpCourseList);
        }
        // 定义一个数组，保存节点状态：0-未搜索；1-搜索中；2-已完成
        int[] state = new int[numCourses];
        boolean canFinish = true;
        // 遍历每一个节点，作为起始点
        for (int i = 0; i < numCourses && canFinish; i++) {
            // 深度搜索；只搜未搜索过的
            if (state[i] == 0) {
                canFinish = canFinish && dfs(followUpCourses, state, i);
            }
        }
        return canFinish;
    }

    // 定义一个辅助方法，进行深度优先搜索
    public boolean dfs(HashMap<Integer, ArrayList<Integer>> followUpCourses, int[] state, int i) {
        state[i] = 1;
        // 遍历所有后续课程，依次递归调用
        for (int followUpCourse : followUpCourses.getOrDefault(i, new ArrayList<>())) {
            if (state[followUpCourse] == 0) {
                if (!dfs(followUpCourses, state, followUpCourse))
                    return false;
            } else if (state[followUpCourse] == 1) {
                return false;
            }
        }
        // 后续课程全部搜索完毕，状态改为2
        state[i] = 2;
        return true;
    }

    public static void main(String[] args) {
        CourseSchedule cs = new CourseSchedule();
        System.out.println(cs.canFinish(2, new int[][]{{1, 0}}));
        System.out.println(cs.canFinish(2, new int[][]{{1, 0}, {0, 1}}));
    }
}
